#include <stdio.h>
#include <stdlib.h>
//最大顶点个数
#define MAX_VERTEX_NUM 20
//顶点数据的类型
#define VertexType int
typedef enum {false, true} bool;

/* https://c.biancheng.net/view/3417.html */

//建立全局变量，保存边的最早开始时间
VertexType ve[MAX_VERTEX_NUM];
//建立全局变量，保存边的最晚开始时间
VertexType vl[MAX_VERTEX_NUM];

typedef struct ArchNode
{
    /* data */
    //邻接点在数组中的位置下标
    int adjvex;
    //指向下一个邻接点的指针
    struct ArchNode * nextarc;
    VertexType dut;
}ArchNode;

typedef struct VNode {
    //顶点的数据域
    VertexType data;
    //指向邻接点的指针
    ArchNode * firstarc;
}VNode, AdjList[MAX_VERTEX_NUM]; //存储各链表头结点的数组

typedef struct {
    //图中顶点及各邻接点数组
    AdjList vertices;
    //记录图中顶点数和边或弧数
    int vexnum, arcnum;
}ALGraph;

//找到顶点对应在邻接表数组中的位置下标
int LocateVex(ALGraph G, VertexType v) {
    for(int i = 0; i < G.vexnum; i++) {
        if(G.vertices[i].data == v) {
            return i;
        }
    }
    return -1;
}

//创建AOE网，构建邻接表
void CreateAOE(ALGraph **G) {
    *G = (ALGraph *)malloc(sizeof(ALGraph));

    scanf("%d,%d", &((*G)->vexnum), &((*G)->arcnum));
    for(int i = 0; i < (*G)->vexnum; i++) {
        scanf("%d", &((*G)->vertices[i].data));
        (*G)->vertices[i].firstarc = NULL;
    }

    VertexType initial, end, dut;
    for(int i = 0; i < (*G)->arcnum; i++) {
        scanf("%d,%d,%d", &initial, &end, &dut);

        ArchNode *p = (ArchNode *)malloc(sizeof(ArchNode));
        p->adjvex = LocateVex(*(*G), end);
        p->nextarc = NULL;
        p->dut = dut;

        int locate = LocateVex(*(*G), initial);
        p->nextarc = (*G)->vertices[locate].firstarc;
        (*G)->vertices[locate].firstarc = p;
    }
}

//创建AOE网，构建邻接表
void CreateAOE1(ALGraph **G) {
    *G=(ALGraph*)malloc(sizeof(ALGraph));
    //输入图含有的顶点数和弧的个数
    (*G)->vexnum = 9;
    (*G)->arcnum = 11;
    //初始化图含有的顶点数据
    for(int i = 0; i < (*G)->vexnum; i++) {
        (*G)->vertices[i].data = i+1;
        (*G)->vertices[i].firstarc = NULL;
    }
    //在邻接表中添加弧的数据
    //V1->V2 6
    ArchNode *p1 = (ArchNode *)malloc(sizeof(ArchNode));
    p1->adjvex = LocateVex(*(*G), 2);
    p1->nextarc = NULL;
    p1->dut = 6;
    int locate = LocateVex(*(*G), 1);
    p1->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p1;
    //V1->V3 4
    ArchNode *p2 = (ArchNode *)malloc(sizeof(ArchNode));
    p2->adjvex = LocateVex(*(*G), 3);
    p2->nextarc = NULL;
    p2->dut = 4;
    locate = LocateVex(*(*G), 1);
    p2->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p2;
    //V1->V4 5
    ArchNode *p3 = (ArchNode *)malloc(sizeof(ArchNode));
    p3->adjvex = LocateVex(*(*G), 4);
    p3->nextarc = NULL;
    p3->dut = 5;
    locate = LocateVex(*(*G), 1);
    p3->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p3;
    //V2->V5 1
    ArchNode *p4 = (ArchNode *)malloc(sizeof(ArchNode));
    p4->adjvex = LocateVex(*(*G), 5);
    p4->nextarc = NULL;
    p4->dut = 1;
    locate = LocateVex(*(*G), 2);
    p4->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p4;
    //V3->V5 1
    ArchNode *p5 = (ArchNode *)malloc(sizeof(ArchNode));
    p5->adjvex = LocateVex(*(*G), 5);
    p5->nextarc = NULL;
    p5->dut = 1;
    locate = LocateVex(*(*G), 3);
    p5->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p5;
    //V4->V6 2
    ArchNode *p6 = (ArchNode *)malloc(sizeof(ArchNode));
    p6->adjvex = LocateVex(*(*G), 6);
    p6->nextarc = NULL;
    p6->dut = 2;
    locate = LocateVex(*(*G), 4);
    p6->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p6;
    //V5->V7 9
    ArchNode *p7 = (ArchNode *)malloc(sizeof(ArchNode));
    p7->adjvex = LocateVex(*(*G), 7);
    p7->nextarc = NULL;
    p7->dut = 9;
    locate = LocateVex(*(*G), 5);
    p7->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p7;
    //V5->V8 7
    ArchNode *p8 = (ArchNode *)malloc(sizeof(ArchNode));
    p8->adjvex = LocateVex(*(*G), 8);
    p8->nextarc = NULL;
    p8->dut = 7;
    locate = LocateVex(*(*G), 5);
    p8->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p8;
    //V6->V8 4
    ArchNode *p9 = (ArchNode *)malloc(sizeof(ArchNode));
    p9->adjvex = LocateVex(*(*G), 8);
    p9->nextarc = NULL;
    p9->dut = 4;
    locate = LocateVex(*(*G), 6);
    p9->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p9;
    //V7->V9 2
    ArchNode *p10 = (ArchNode *)malloc(sizeof(ArchNode));
    p10->adjvex = LocateVex(*(*G), 9);
    p10->nextarc = NULL;
    p10->dut = 2;
    locate = LocateVex(*(*G), 7);
    p10->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p10;
    //V8->V9 4
    ArchNode *p11 = (ArchNode *)malloc(sizeof(ArchNode));
    p11->adjvex = LocateVex(*(*G), 9);
    p11->nextarc = NULL;
    p11->dut = 4;
    locate = LocateVex(*(*G), 8);
    p11->nextarc = (*G)->vertices[locate].firstarc;
    (*G)->vertices[locate].firstarc = p11;
}

//结构体定义栈结构
typedef struct stack {
    VertexType data;
    struct stack * next;
}stack;

stack *T;

//初始化栈结构
void initStack(stack **S) {
    (*S) = (stack *)malloc(sizeof(stack));
    (*S)->next = NULL;
}

//判断栈是否为空
bool StackEmpty(stack S) {
    if(S.next == NULL) {
        return true;
    }
    return false;
}

//进栈，以头插法将新结点插入到链表中
void push(stack *S, VertexType u) {
    stack *p = (stack *)malloc(sizeof(stack));
    p->data = u;
    p->next = NULL;
    p->next = S->next;
    S->next = p;
}

//弹栈函数，删除链表首元结点的同时，释放该空间，并将该结点中的数据域通过地址传值给变量i;
void pop(stack *S, VertexType *i) {
    stack *p = S->next;
    *i = p->data;
    S->next = S->next->next;
    free(p);
}

//统计各顶点的入度
void FindInDegree(ALGraph G, int indegree[]) {
    //初始化数组，默认初始值全部为0
    for(int i = 0; i < G.vexnum; i++) {
        indegree[i] = 0;
    }
    //遍历邻接表，根据各链表中结点的数据域存储的各顶点位置下标，在indegree数组相应位置+1
    for(int i = 0; i < G.vexnum; i++) {
        ArchNode *p = G.vertices[i].firstarc;
        while (p)
        {
            /* code */
            indegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
}

bool TopologicalOrder(ALGraph G) {
    //创建记录各顶点入度的数组
    int indegree[G.vexnum];
    //统计各顶点的入度
    FindInDegree(G, indegree);
    //建立栈结构，程序中使用的是链表
    stack *S;
    //初始化栈
    initStack(&S);
    for(int i = 0; i < G.vexnum; i++) {
        ve[i] = 0;
    }
    //查找度为0的顶点，作为起始点
    for(int i = 0; i < G.vexnum; i++) {
        if(!indegree[i]) {
            push(S, i);
        }
    }
    int count = 0;
    //栈为空为结束标志
    while (!StackEmpty(*S))
    {
        /* code */
        int index;
        //弹栈，并记录栈中保存的顶点所在邻接表数组中的位置
        pop(S, &index);
        //压栈，为求各边的最晚开始时间做准备
        push(T, index);
        ++count;
        //依次查找跟该顶点相链接的顶点，如果初始入度为1，当删除前一个顶点后，该顶点入度为0
        for(ArchNode *p = G.vertices[index].firstarc; p; p = p->nextarc) {
            VertexType k = p->adjvex;
            if(!(--indegree[k])) {
                //顶点入度为0，入栈
                push(S, k);
            }
            //如果边的源点的最长路径长度加上边的权值比汇点的最长路径长度还长，就覆盖ve数组中对应位置的值，最终结束时，ve数组中存储的就是各顶点的最长路径长度
            if(ve[index] + p->dut > ve[k]) {
                ve[k] = ve[index] + p->dut;
            }
        }
    }
    //如果count值小于顶点数量，表明有向图有环
    if(count < G.vexnum) {
        printf("该图有回路");
        return false;
    }
    return true;    
}

//求各顶点的最晚发生时间并计算出各边的最早和最晚开始时间
void Criticalpath(ALGraph G) {
    if(!TopologicalOrder(G)) {
        return;
    }
    for(int i = 0; i < G.vexnum; i++) {
        vl[i] = ve[G.vexnum - 1];
    }
    int j, k;
    while (!StackEmpty(*T))
    {
        /* code */
        pop(T, &j);
        for(ArchNode *p = G.vertices[j].firstarc; p; p = p->nextarc) {
            k = p->adjvex;
            //构建Vl数组，在初始化时，Vl数组中每个单元都是18，如果每个边的汇点-边的权值比源点值小，就保存更小的
            if(vl[k] - p->dut < vl[j]) {
                vl[j] = vl[k] - p->dut;
            }
        }
    }
    for(j = 0; j < G.vexnum; j++) {
        for(ArchNode *p = G.vertices[j].firstarc; p; p = p->nextarc) {
            k = p->adjvex;
            //求各边的最早开始时间e[i],等于ve数组中相应源点存储的值
            int ee = ve[j];
            //求各边的最晚开始时间l[i]，等于汇点在vl数组中存储的值减改边的权值
            int el = vl[k] - p->dut;
            //判断e[i]和l[i]是否相等，如果相等，该边就是关键活动，相应的用*标记；反之，边后边没标记
            char tag = (ee == el)?'*':' ';
            printf("%3d %3d %3d %3d %3d %2c\n", j, k, p->dut, ee, el, tag);
        }
    }
    
}

int main(int argc, char * argv[]) {
    ALGraph *G;
    //创建AOE网
    CreateAOE1(&G);
    initStack(&T);
    TopologicalOrder(*G);
    Criticalpath(*G);
    return 0;
}